package com.zhangx.datastructure.search;

/**
 * @ClassName OrderTable
 * @Description 有序表
 * @Author zhangx
 * @Date 2021/1/22 8:51
 **/
public class OrderTable {

    public int[] a = new int[]{0,1,16,24,35,47,59,62,73,88,99};
    public int[] a2 = new int[]{0,1,16,24,35,47,59,62,73,88,99,0,0};

//    菲波那切数列
    public int[] F = new int[11];
    /**
     * 折半查找&差值优化
     * 前提是数据有序
     * O(logn)
     * @return
     */
    public int binarySearch(int[] arr,int key){
        int low = 1;
        int high = arr.length-1;
        while (low<=high){

            int mid = (low+high)/2;
//            差值优化，不再是折半了，当数据比较均匀效率高
            mid = low + (high-low)*(key-a[0])/(a[arr.length-1]-a[0]);
            if (key < arr[mid]){
                high = mid-1;
            }else if(key > arr[mid]){
                low = mid+1;
            }else {
                return mid;
            }
        }
        return 0;

    }

    public int initFibonacci(int n){
        if (n==0){
            F[0] = 0;
            return 0;
        }else if(n==1){
            F[1] = 1;
            return 1;
        }else {
            int d = initFibonacci(n-1)+initFibonacci(n-2);
            F[n] = d;
            return d;
        }
    }

    /**
     * 斐波那契查找
     * 看P306的图，本质上也是找中间点
     * @param arr
     * @param n
     * @param key
     * @return
     */
    public int fibonacciSearch(int[] arr,int n ,int key){
        int low = 1;
        int high = n;
        int k = 0;//斐波那契数组下标
        int mid = 0;
        while (n>F[k]-1){
            k++;
        }
        for (int i = n ; i < F[k]-1; i++) {//计算n 在菲波那切数列的位置
            arr[i] = arr[n];//将不满的数值补全，注意会溢出可能
        }
        while (low <= high){
            System.out.println("k="+k);
            mid = low + F[k-1] + 1;
            System.out.println(mid);
            if (key < arr[mid]){
                high = mid - 1;
                k = k-1;
            }else if (key > arr[mid]){
                low = mid + 1;
                k = k-2;
            }else {
                if (mid<=n){
                    return mid;//找到了
                }else {
                    return n;//补全数值
                }
            }
        }
//        找不到
        return 0;
    }

    public static void main(String[] args) {
        OrderTable orderTable = new OrderTable();
        int index = orderTable.binarySearch(orderTable.a,62);
        System.out.println(index);

        orderTable.initFibonacci(10);

        index = orderTable.fibonacciSearch(orderTable.a2,10,59);
        System.out.println(index);

    }
}
